//
//  Solution.hpp
//  Node
//
//  Created by zhangjikuan on 2020/12/3.
//  Copyright © 2020 hsgd. All rights reserved.
//

#ifndef Solution_hpp
#define Solution_hpp

#include <stdio.h>
#include <vector>
#include <unordered_map>

using namespace std;
class Solution {
    unordered_map<int, string> map;
    struct ListNode {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };
     
public:

    // 1 最大桶面积
    int maxArea(vector<int>& height);
    // 2. 正则规则匹配
    bool isMatch(string s, string p);
    // 3. 排序数组去重 前提条件是这个数组是已经排好序的需要的是遍历
    int removeDuplicates(vector<int>& nums);
    // 4. 买卖股票的最佳时机 II
    int maxProfit(vector<int>& prices);
    // 5. LeetCode 给出官方 动态规划
    int maxProfit2(vector<int>& prices);
    // 6. 旋转数组
    /*
     实例1
     输入: [1,2,3,4,5,6,7] 和 k = 3
     输出: [5,6,7,1,2,3,4]
     解释:
     向右旋转 1 步: [7,1,2,3,4,5,6]
     向右旋转 2 步: [6,7,1,2,3,4,5]
     向右旋转 3 步: [5,6,7,1,2,3,4]

     实例2
     输入: [-1,-100,3,99] 和 k = 2
     输出: [3,99,-1,-100]
     解释:
     向右旋转 1 步: [99,-1,-100,3]
     向右旋转 2 步: [3,99,-1,-100]

     */
    void rotate(vector<int>& nums, int k);
    
    // 7. 只出现了一次的元素
    /*
    给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

    说明：

    你的算法应该具有线性时间复杂度 O(N)。 你可以不使用额外空间来实现吗？
     */
    int singleNumber(vector<int>& nums);
    /*
     8. 给定两个数组，编写一个函数来计算它们的交集。
     */
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2);
    
    // 9.
    /*
     给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

     最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

     你可以假设除了整数 0 之外，这个整数不会以零开头。
     示例 1：

     输入：digits = [1,2,3]
     输出：[1,2,4]
     解释：输入数组表示数字 123。
     示例 2：

     输入：digits = [4,3,2,1]
     输出：[4,3,2,2]
     解释：输入数组表示数字 4321。
     示例 3：

     输入：digits = [0]
     输出：[1]
      

     提示：

     1 <= digits.length <= 100
     0 <= digits[i] <= 9

     */
    vector<int> plusOne(vector<int>& digits);
    
    // 10.
    /*
     给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

     示例:

     输入: [0,1,0,3,12]
     输出: [1,3,12,0,0]
     说明:

     必须在原数组上操作，不能拷贝额外的数组。
     尽量减少操作次数。
     */
    void moveZeroes(vector<int>& nums);
    
    // 11.
    /*
     给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

     你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

      

     示例:

     给定 nums = [2, 7, 11, 15], target = 9

     因为 nums[0] + nums[1] = 2 + 7 = 9
     所以返回 [0, 1]

     作者：力扣 (LeetCode)
     链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2jrse/
     来源：力扣（LeetCode）
     著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    vector<int> twoSum(vector<int>& nums, int target);
    /// 12. 9x9 是否是有效数独
    /*
     判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

     数字 1-9 在每一行只能出现一次。
     数字 1-9 在每一列只能出现一次。
     数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。


     上图是一个部分填充的有效的数独。

     数独部分空格内已填入了数字，空白格用 '.' 表示。

     示例 1:

     输入:
     [
       ["5","3",".",".","7",".",".",".","."],
       ["6",".",".","1","9","5",".",".","."],
       [".","9","8",".",".",".",".","6","."],
       ["8",".",".",".","6",".",".",".","3"],
       ["4",".",".","8",".","3",".",".","1"],
       ["7",".",".",".","2",".",".",".","6"],
       [".","6",".",".",".",".","2","8","."],
       [".",".",".","4","1","9",".",".","5"],
       [".",".",".",".","8",".",".","7","9"]
     ]
     输出: true
     示例 2:

     输入:
     [
       ["8","3",".",".","7",".",".",".","."],
       ["6",".",".","1","9","5",".",".","."],
       [".","9","8",".",".",".",".","6","."],
       ["8",".",".",".","6",".",".",".","3"],
       ["4",".",".","8",".","3",".",".","1"],
       ["7",".",".",".","2",".",".",".","6"],
       [".","6",".",".",".",".","2","8","."],
       [".",".",".","4","1","9",".",".","5"],
       [".",".",".",".","8",".",".","7","9"]
     ]
     输出: false
     解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
          但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
     说明:

     一个有效的数独（部分已被填充）不一定是可解的。
     只需要根据以上规则，验证已经填入的数字是否有效即可。
     给定数独序列只包含数字 1-9 和字符 '.' 。
     给定数独永远是 9x9 形式的。


     作者：力扣 (LeetCode)
     链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2f9gg/
     来源：力扣（LeetCode）
     著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    bool isValidSudoku(vector<vector<char>>& board);
    
    // 13.
    /*
     给定一个 n × n 的二维矩阵表示一个图像。

     将图像顺时针旋转 90 度。

     说明：

     你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

     示例 1:

     给定 matrix =
     [
       [1,2,3],
       [4,5,6],
       [7,8,9]
     ],

     原地旋转输入矩阵，使其变为:
     [
       [7,4,1],
       [8,5,2],
       [9,6,3]
     ]
     示例 2:

     给定 matrix =
     [
       [ 5, 1, 9,11],
       [ 2, 4, 8,10],
       [13, 3, 6, 7],
       [15,14,12,16]
     ],

     原地旋转输入矩阵，使其变为:
     [
       [15,13, 2, 5],
       [14, 3, 4, 1],
       [12, 6, 8, 9],
       [16, 7,10,11]
     ]

     作者：力扣 (LeetCode)
     链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnhhkv/
     来源：力扣（LeetCode）
     著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    void rotate(vector<vector<int>>& matrix);
    // 14.
    void reverseString(vector<char>& s);
    // 15.
    int reverse(int x);
    // 16.
    int firstUniqChar(string s);
    // 17.
    bool isAnagram(string s, string t);
    // 18.
    bool isPalindrome(string s);
    // 19.
    int myAtoi(string s);
    
    // 20.
    /*
     给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
     示例 1:

     输入: haystack = "hello", needle = "ll"
     输出: 2
     示例 2:

     输入: haystack = "aaaaa", needle = "bba"
     输出: -1
     说明:

     当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

     对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

     相关标签


     作者：力扣 (LeetCode)
     链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnr003/
     来源：力扣（LeetCode）
     著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    int strStr(string haystack, string needle);
    
    // 21. 如何快速的KMP 的 next 数组
    // 求next数组的过程完全可以看成字符串匹配的过程，即以模式字符串为主字符串，
    // 以模式字符串的前缀为目标字符串，一旦字符串匹配成功，那么当前的next值就是匹配成功的字符串的长度。
    //具体来说，就是从模式字符串的第一位(注意，不包括第0位)开始对自身进行匹配运算。
    // 在任一位置，能匹配的最长长度就是当前位置的next值。如下图所示。
    /*
         i  next[2] = 0
     [a][b][a][b][a][b][c][a]
        [a][b][a][b][a][b][c][a]
         j

            (A)
     
     i = i + 1
     
           i next[3] = 1
    [a][b][a][b][a][b][c][a]
          [a][b][a][b][a][b][c][a]
           j
     
            (B)
      
     i = i + 1
     j = j + 1
          
              i next[4] = 2
    [a][b][a][b][a][b][c][a]
          [a][b][a][b][a][b][c][a]
              j
            (C)

     重复 C上的移动     next[5] = 3
                    i next[6] = 4
    [a][b][a][b][a][b][c][a]
          [a][b][a][b][a][b][c][a]
                    j
            (D)

     
                       i next[7] = 0
    [a][b][a][b][a][b][c][a]
                      [a][b][a][b][a][b][c][a]
                       j
            (D)

     
     */

    vector<int> getNext(string needle);
    
    int strStrKMP(string haystack, string needle);
    
    // 22.
    /*
     给定一个正整数 n ，输出外观数列的第 n 项。

     「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

     你可以将其视作是由递归公式定义的数字字符串序列：

     countAndSay(1) = "1"
     countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
     前五项如下：

     1.     1
     2.     11
     3.     21
     4.     1211
     5.     111221
     第一项是数字 1
     描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
     描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
     描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
     描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"
     要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

     例如，数字字符串 "3322251" 的描述如下图：
     3个3 3个2 1个5 1个1
     33321511

     
     **/
    
    string countAndSay(int n);
    
    // 最长公共串
    string longestCommonPrefix(vector<string>& strs);
    
    ListNode* reverseList(ListNode* head) {
        
        if (head==NULL || head->next == NULL) {
            return head;
        }
  
        // 初始化
        ListNode *p,*q;
        p = head->next;
        head->next = NULL;
        while (p!=NULL) {
            q = p;
            p = q->next;
            q->next = head;
            head = q;
        }
        return head;
        ListNode *ret = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return ret;
        
    }
    
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n);
    
    /// 23. 二维数组 矩阵转换
    /// @param matrix 二维数组
    /// 示例 1：
   /*
    输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
    输出：[[1,4,7],[2,5,8],[3,6,9]]
    示例 2：

    输入：matrix = [[1,2,3],[4,5,6]]
    输出：[[1,4],[2,5],[3,6]] */
    vector<vector<int>> transpose(vector<vector<int>>& matrix);
    
    /// 24. 数组中重复的数字
    /// @param nums 数组
    int findRepeatNumber(vector<int>& nums);
    
   // 25.
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target);
    
    int partition(vector<int>& nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j<=r-1; j++) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums[i], nums[j]);
            }
        }
        
        swap(nums[i+1], nums[r]);
        return i + 1;
    }
    
    int randomized_partition(vector<int>& nums, int l, int r) {
        int i = rand() % (r - l + 1) + l; // 随机选一个作为我们的主元
        swap(nums[r], nums[i]);
        return partition(nums, l, r);
    }
    void randomized_quicksort(vector<int>& nums, int l, int r) {
        if (l < r) {
            int pos = randomized_partition(nums, l, r);
            randomized_quicksort(nums, l, pos - 1);
            randomized_quicksort(nums, pos + 1, r);
        }
    }
    
public:
    vector<int> sortArray(vector<int>& nums) {
        srand((unsigned)time(NULL));
        randomized_quicksort(nums, 0, (int)nums.size() - 1);
        return nums;
    }
    
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        
        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return {};
        }

        vector<int> order;
        
        int rows = (int)matrix.size();
        int columns = (int)matrix[0].size();
        
        // 其实是一个遍历的顺序放在数组中
        // 上 下 左 右
      
        int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
        
        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column++) {
                order.push_back(matrix[top][column]);
            }
            
            for (int row = top + 1; row <= bottom; row++) {
                order.push_back(matrix[row][right]);
            }
            
            if (left < right && top < bottom) {
                for (int column = right - 1; column > left; column--) {
                    order.push_back(matrix[bottom][column]);
                }
                for (int row = bottom; row > top; row --) {
                    order.push_back(matrix[row][left]);
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        
        
        
        
        return order;
    }
  
};


#endif /* Solution_hpp */
